#include "nfa.h"
#include"namestorage.h"

using std::multimap;
using std::vector;
using std::map;
using std::string;
using std::set;
using std::pair;
using std::make_pair;
using std::endl;
using std::cout;

set<unsigned> NFA::allStates() const {
        set<unsigned> res = setUnion(accepting, starting);
        multimap<pair<unsigned, char>, unsigned>::const_iterator it = rules.begin();
        for( ; it != rules.end(); ++it ) {
                res.insert((it -> first) . first);
                res.insert(it -> second);
        }
        return res;
}

set<unsigned> NFA::feedTerminal(unsigned state, char terminal) const {
        set<unsigned> res;
        if (state != 0) {
                multimap<pair<unsigned, char>, unsigned>::const_iterator it = rules . lower_bound(make_pair(state, terminal)),
                                                                                                                        to = rules . upper_bound(make_pair(state, terminal));
                for ( ; it != to ; ++it)
                        res . insert(it -> second);
        }
        if ((terminal != 0) && !epsilonFree)
                res = epsilonExpand(res);
        return res;
}

set<unsigned> NFA::feedTerminal(set<unsigned> const & states, char terminal) const {
        set<unsigned> estates = (epsilonFree || (terminal == 0)) ? states : epsilonExpand(states);
        set<unsigned> res;
        set<unsigned>::const_iterator it = estates . begin();
        for( ; it != estates . end(); ++it ) {
                set<unsigned> to = feedTerminal(*it, terminal);
                res = setUnion(res, to);
        }
        if ((terminal != 0) && !epsilonFree)
                res = epsilonExpand(res);
        return res;
}

set<unsigned> NFA::feedAnyOfThe(set<unsigned> const & states, set<char> const & charset) const {
        set<unsigned> res;
        for( set<char>::const_iterator it = charset . begin(); it != charset . end(); ++it )
                res = setUnion(res, feedTerminal(states, *it));
        return res;
}

set<unsigned> NFA::epsilonExpand(set<unsigned> const & states) const {
        if (epsilonFree)
                return states;
        set<unsigned> res = states;
        unsigned size = res . size(), prevSize = 0;
        do {
                std::swap(prevSize, size);
                res = setUnion(feedTerminal(res, 0), res);
                size = res . size();
        } while (size != prevSize);
        return res;
}

set<unsigned> NFA::feedString(unsigned state, string const & str) const {
        string::const_iterator it = str . begin();
        set<unsigned> res;
        res . insert(state);
        for( ; (!res . empty()) && (it != str . end()); ++it )
                res = feedTerminal(res, *it);
        return res;
}

set<unsigned> NFA::feedString(set<unsigned> const & states, std::string const & str) const {
        set<unsigned> res = states;
        string::const_iterator it = str . begin();
        for( ; (!res . empty()) && (it != str . end()); ++it )
                res = feedTerminal(res, *it);
        return res;
}

set<unsigned> const & NFA::startingState() const {
        return starting;
}

set<unsigned> const & NFA::acceptingStates() const {
        return accepting;
}

bool NFA::isAccepting(unsigned state) const {
        return (accepting . find(state) != accepting . end());
}

bool NFA::isAccepting(set<unsigned> const & states) const {
        set<unsigned> big = (states . size() > accepting . size()) ? states : accepting,
                                small = (states . size() > accepting . size()) ? accepting : states;
        set<unsigned>::const_iterator it = small . begin();
        bool res = false;
        for( ; !res && (it != small . end()) ; ++it )
                res = (big . find(*it) != big . end());
        return res;
}

std::istream & operator>>(std::istream & in, NFA &nfa) {        
        string start;
        getline(in, start);
        unsigned pos = start . find_first_of(',');
        while (pos != string::npos) {
                nfa . starting . insert (NFA::names . addName(NFA::extractAlNum(start . substr(0, pos))));
                start = start . substr(pos + 1);
                pos = start . find_first_of(',');
        }
        if (NFA::extractAlNum(start) . length() != 0)
                nfa . starting . insert(NFA::names . addName(NFA::extractAlNum(start)));
        getline(in, start);
        pos = start . find_first_of(',');
        while (pos != string::npos) {
                nfa . accepting . insert (NFA::names . addName(NFA::extractAlNum(start . substr(0, pos))));
                start = start . substr(pos + 1);
                pos = start . find_first_of(',');
        }
        if (NFA::extractAlNum(start) . length() != 0)
                nfa . accepting . insert(NFA::names . addName(NFA::extractAlNum(start)));
        while (in . good()) {
                //std::cout << 1 << std::endl;
                pair<pair<unsigned, char>, unsigned> newRule = NFA::extractRuleFromStream(in);
                if (newRule . second != 0) {
                	nfa . rules . insert(newRule);
                	if (newRule . first . second == 0)
                        	nfa . epsilonFree = false;
                }
                //std::cout << nfa.rules[nfa.rules.size()-1].from << " " << nfa.rules[nfa.rules.size()-1].on << " " << nfa.rules[nfa.rules.size()-1].to << std::endl;
                //std::cout << newRule.from << " " << newRule.on << " " << newRule.to << std::endl;
        }
        return in;
}

std::ostream & operator<<(std::ostream &stream, NFA const & nfa) {
        stream << "digraph NFA {" << endl;
        for( set<unsigned>::const_iterator it = nfa . accepting . begin(); it != nfa . accepting . end(); ++it )
                stream << "\"" << NFA::names[*it] << ((nfa . starting . find(*it) != nfa . starting . end()) ? "\" [style = filled, color = yellow];" : "\" [style = filled, color = red];") << endl;
        for( set<unsigned>::const_iterator it = nfa . starting . begin(); it != nfa . starting . end(); ++it )
                if (nfa . accepting . find(*it) == nfa . accepting . end())
                        stream << "\"" << NFA::names[*it] << "\" [style = filled, color = green];" << endl;
        for( multimap<pair<unsigned, char>, unsigned>::const_iterator it = nfa . rules . begin(); it != nfa . rules . end(); ++it )
                stream << "\"" << NFA::names[it -> first . first] << "\" -> \"" << NFA::names[it -> second] << "\" [label = \"" << ((it -> first . second) ? (it -> first . second) : ' ') << "\"];" << endl;
        stream << "}" << endl;
        return stream;
}

void NFA::renameStates(unsigned from, unsigned to) const {
        multimap<pair<unsigned, char>, unsigned> newRules;
        pair<pair<unsigned, char>, unsigned> rule;
        for( multimap<pair<unsigned, char>, unsigned>::iterator it = rules . begin(); it != rules . end(); ++it ) {
                rule = *it;
                if (rule . first . first == from)
                        rule . first . first = to;
                if (rule . second == from)
                        rule . second = to;
                newRules . insert(rule);
        }
        rules = newRules;
        if (accepting . erase(from) != 0)
                accepting . insert(to);
        if (starting . erase(from) != 0)
                starting . insert(to);
}

void NFA::renameStates(map<unsigned, unsigned> const & m) const {
        multimap<pair<unsigned, char>, unsigned> newRules;
        map<unsigned, unsigned>::const_iterator subst;
        for( multimap<pair<unsigned, char>, unsigned>::iterator it = rules . begin(); it != rules . end(); ++it ) {
                pair<pair<unsigned, char>, unsigned> rule;
                rule = *it;
                subst = m . find(rule . first . first);
                if (subst != m . end())
                        rule . first . first = subst  -> second;
                subst = m . find(rule . second);
                if (subst != m . end())
                        rule . second = subst  -> second;
                newRules . insert(rule);
        }
        rules = newRules;
        set<unsigned> newAccepting;
        for (set<unsigned>::const_iterator it = accepting . begin(); it != accepting . end(); ++it ) {
                subst = m . find(*it);
                if (subst != m . end())
                        newAccepting . insert (subst  -> second);
                else
                        newAccepting . insert(*it);
        }
        accepting = newAccepting;
        set<unsigned> newStarting;
        for (set<unsigned>::const_iterator it = starting . begin(); it != starting . end(); ++it ) {
                subst = m . find(*it);
                if (subst != m . end())
                        newStarting . insert (subst  -> second);
                else
                        newStarting . insert(*it);
        }
        starting = newStarting;
}

NFA & NFA::operator=(NFA const & nfa) {
        starting = nfa . starting;
        accepting = nfa . accepting;
        rules = nfa . rules;
        epsilonFree = nfa . epsilonFree;
        return *this;
}

void NFA::resolveConflict(set<unsigned> stoplist) const {
        map<unsigned, unsigned> rename;
        set<unsigned> all = allStates();
        unsigned renNum = 0;
        for( set<unsigned>::const_iterator it = all . begin(); it != all . end(); ++it )
                if (stoplist . find(*it) != stoplist . end()) {
                        renNum = names . resolveConflict(stoplist, names[*it]);
                        rename . insert(make_pair(*it, renNum));
                        stoplist . insert(renNum);
                }
        renameStates(rename);
}

NFA NFA::operator+(NFA const & nfa) const {
        NFA nfaRes(*this);
        nfaRes . resolveConflict(nfa . allStates());
        for( multimap<pair<unsigned, char>, unsigned>::const_iterator it = nfa . rules . begin() ; it != nfa . rules . end(); ++it )
                nfaRes . rules . insert(*it);
        for( set<unsigned>::const_iterator it = nfa . starting . begin(); it != nfa . starting . end(); ++it )
                for( set<unsigned>::const_iterator it2 = nfaRes . accepting . begin(); it2 != nfaRes . accepting . end(); ++it2 )
                        nfaRes . rules . insert(make_pair(make_pair(*it2, 0), *it));
        nfaRes . accepting = nfa . accepting;
        nfaRes . epsilonFree = false;
        return nfaRes;
}

NFA NFA::operator|(NFA const & nfa) const {
	NFA nfaRes(*this);
	nfaRes . resolveConflict(nfa . allStates());
	for( multimap<pair<unsigned, char>, unsigned>::const_iterator it = nfa . rules . begin() ; it != nfa . rules . end(); ++it )
		nfaRes . rules . insert(*it);

	string newStartName = names[0] + "_";
	int newStarting = names.addOrRename(newStartName);

	for( set<unsigned>::const_iterator it = nfaRes . starting . begin(); it != nfaRes . starting . end(); ++it )
			nfaRes . rules . insert(make_pair(make_pair(newStarting, 0), *it));

	for( set<unsigned>::const_iterator it = nfa . starting . begin(); it != nfa . starting . end(); ++it )
			nfaRes . rules . insert(make_pair(make_pair(newStarting, 0), *it));

	nfaRes . starting. clear();
	nfaRes . starting . insert(newStarting);

	string newAcceptName = names[0] + "_";
	int newAccepting = names.addOrRename(newAcceptName);

	for( set<unsigned>::const_iterator it = nfaRes . accepting. begin(); it != nfaRes . accepting . end(); ++it )
			nfaRes . rules . insert(make_pair(make_pair(*it, 0), newAccepting));

	for( set<unsigned>::const_iterator it = nfa . accepting . begin(); it != nfa . accepting . end(); ++it )
			nfaRes . rules . insert(make_pair(make_pair(*it, 0), newAccepting));

	nfaRes . accepting . clear();
	nfaRes . accepting . insert(newStarting);

	nfaRes . epsilonFree = false;
	return nfaRes;
}

NFA NFA::operator*() const {
	NFA nfaRes(*this);
	nfaRes . epsilonFree = false;
	unsigned newstart = NFA::names . addOrRename("K");
	for( set<unsigned>::const_iterator its = starting . begin(); its != starting . end() ; ++its ) {
		for( set<unsigned>::const_iterator ita = accepting . begin(); ita != accepting . end() ; ++ita ) {
			if (!ruleExists(make_pair(*ita, 0), *its))
				nfaRes . rules . insert(make_pair(make_pair(*ita, 0), *its));
		}
		nfaRes . rules . insert(make_pair(make_pair(newstart, 0), *its));
	}
	nfaRes . starting = set<unsigned>();
	nfaRes . starting . insert(newstart);
	nfaRes . accepting . insert(newstart);
	return nfaRes;
}

NFA & NFA::operator+=(NFA const & nfa) {
        return operator=((*this) + nfa);
}

set<char> NFA::apparentAlphabet() const {
        set<char> res;
        for ( multimap<pair<unsigned, char>, unsigned>::const_iterator it = rules . begin() ; it != rules . end(); ++it )
                res . insert(it -> first . second);
        res . erase(0);
        return res;
}

set<unsigned> NFA::reachableStatesFrom(set<unsigned> const & from) const {
        set<unsigned> res = from;
        set<char> charset = apparentAlphabet();
        unsigned size = res . size(), prevSize = 0;
        do {
                std::swap(prevSize, size);
                res = setUnion(feedAnyOfThe(res, charset), res);
                size = res . size();
        } while (size != prevSize);
        return res;
}

set<unsigned> NFA::reachableStates() const {
	return reachableStatesFrom(starting);
}

bool NFA::ruleExists(pair<unsigned, char> const & key, unsigned to) const {
        pair<multimap<pair<unsigned, char>, unsigned>::const_iterator, multimap<pair<unsigned, char>, unsigned>::const_iterator> range = rules . equal_range(key);
        bool res = false;
        for ( multimap<pair<unsigned, char>, unsigned>::const_iterator it = range . first; !res && (it != range . second); ++it )
                res = (it -> second == to);
        return res;
}

void NFA::duplicateLinks(unsigned source, unsigned dest) {
        if (starting . find(source) != starting . end())
                starting . insert(dest);
        if (accepting . find(dest) != accepting . end())
                accepting . insert(source);
        multimap<pair<unsigned, char>, unsigned> copyRules = rules;
        for ( multimap<pair<unsigned, char>, unsigned>::const_iterator it = copyRules . begin() ; it != copyRules . end(); ++it ) {
                if (it -> second == source) {
                        pair<pair<unsigned, char>, unsigned> rule = *it;
                        rule . second = dest;
                        if (!ruleExists(rule . first, rule . second))
                                rules . insert(rule);
                }
        }                       
}

void NFA::eliminateEpsilon() {
        if (epsilonFree)
                return;
        unsigned prevSize = 0, size = rules . size() + accepting . size() + starting . size();
        multimap<pair<unsigned, char>, unsigned> oldRules;
        do {
                std::swap(prevSize, size);
                oldRules = rules;
                for ( multimap<pair<unsigned, char>, unsigned>::const_iterator it = oldRules . begin() ; it != oldRules . end(); ++it ) {
                        if (it -> first . second == 0)
                                duplicateLinks(it -> first . first, it -> second);
                }
                size = rules . size() + accepting . size() + starting . size();
        } while (size > prevSize);
        for ( multimap<pair<unsigned, char>, unsigned>::iterator it = rules . begin() ; it != rules . end(); ) {
                if (it -> first . second == 0)
                        rules . erase(it++);
                else
                        ++it;
        }
}



DFA NFA::determinate() const {	
	DFA dfa;
	map<set<unsigned>, unsigned, CompareSet> setmap;
	map<unsigned, set<unsigned> >  mapset;
	set<char> alpha = apparentAlphabet();
	setmap . insert(make_pair(set<unsigned>(), 0));
	mapset . insert(make_pair(0, set<unsigned>()));
	unsigned newset = names . addOrRename(concatName(starting));
	setmap . insert(make_pair(starting, newset));
	mapset . insert(make_pair(newset, starting));
	dfa . starting = newset;
	if (isAccepting(starting))
		dfa . accepting . insert(newset);
	unsigned prevSize = 0, size = dfa . rules . size() + dfa . accepting . size();
	do {
		std::swap(prevSize, size);
		map<unsigned, set<unsigned> >  mapset2 = mapset;
		map<unsigned, set<unsigned> >::const_iterator it = ++mapset2 . begin();
		for( ; it != mapset2 . end(); ++it ) {
			set<char>::const_iterator itc = alpha . begin();
			for( ; itc != alpha . end(); ++itc ) {
				set<unsigned> state = feedTerminal(it -> second, *itc);
				if (!state . empty()) {
					if (setmap . find(state) == setmap . end()) {
						unsigned newset = names . addOrRename(concatName(state));
						setmap . insert(make_pair(state, newset));
						mapset . insert(make_pair(newset, state));
						if (isAccepting(state))
							dfa . accepting . insert(newset);
					}
					dfa . rules . insert(make_pair(make_pair(it -> first, *itc), setmap[state]));
				}
			}
		}
		size = dfa . rules . size() + dfa . accepting . size();
		mapset2 = mapset;
	} while (prevSize < size);
	return dfa;
}

NFA NFA::regularGrammar() const {
	NFA res(*this);
	if (res . starting . size() != 1) {
		unsigned newstate = names . addOrRename("RS");
		set<unsigned>::const_iterator it = starting . begin();
		for( ; it != starting . end(); ++it)
			res . rules . insert(make_pair(make_pair(newstate, 0), *it));
		res . starting = set<unsigned>();
		res . starting . insert(newstate);
	}
	if (reachableStatesFrom(accepting) . size() != accepting . size() ||
			accepting . size() != 1) {
		unsigned newstate = names . addOrRename("RF");
		set<unsigned>::const_iterator it = accepting . begin();
		for( ; it != accepting . end(); ++it)
			res . rules . insert(make_pair(make_pair(*it, 0), newstate));
		res . accepting = set<unsigned>();
		res . accepting . insert(newstate);
	}
	//cout << res;
	return res;
}	

RegExp * NFA::toRegExp() const {
	return regularGrammar() . _toRegExp();
}

RegExp * NFA::_charSetToRegExp(set<char> const & charset) {
	if (charset . size() == 0) return new EmptyRegExp();
	string temp;
	if (*charset.begin()) 
		temp . push_back(*charset . begin());
	if (charset . size() == 1) return new LiteralRegExp(temp);
	set<char> charset2 = charset;
	charset2 . erase(charset2 . begin());
	return new AlterRegExp(new LiteralRegExp(temp), _charSetToRegExp(charset2));
}

//if applystate != tostate, applymap must not contain applystate
void NFA::_applyREMap(unsigned applystate, map<unsigned, RegExp *> const & applymap,
				unsigned tostate, map<unsigned, RegExp *> & tomap) const {
	if (tomap . find(applystate) != tomap . end()) {
		if (applystate != tostate) {
			RegExp * prefix = tomap[applystate];
			for( map<unsigned, RegExp *>::const_iterator it = applymap . begin();
											it != applymap . end(); ++it ) {
				if (tomap . find(it -> first) != tomap . end()) {
					tomap[it -> first] = new AlterRegExp(tomap[it -> first],
							new ConcatRegExp(prefix -> copy(), it -> second -> copy()));
				} else {
					tomap[it -> first] = new ConcatRegExp(prefix -> copy(),
									it -> second -> copy());
				}
			}
			if (isAccepting(applystate)) {
				if (tomap . find(0) != tomap . end()) {
					tomap[0] = new AlterRegExp(prefix -> copy(), tomap[0]);
				} else {
					tomap[0] = prefix -> copy();
				}
			}
			delete prefix;
			tomap . erase(applystate);
		} else {
			RegExp * prefix = tomap[tostate];
			for( map<unsigned, RegExp *>::iterator it = tomap . begin();
										it != tomap . end(); ++it ) {
				if (it -> first != tostate)
					tomap[it -> first] = new ConcatRegExp(new KleeneRegExp(prefix -> copy()),
												it -> second);
			}
			if (isAccepting(tostate)) {
				if (tomap . find(0) != tomap . end()) {
					tomap[0] = new ConcatRegExp(new KleeneRegExp(prefix -> copy()),
												tomap[0]);
				} else {
					tomap[0] = new KleeneRegExp(prefix -> copy());
				}
			}
			delete prefix;
			tomap . erase(tostate);
		}
	} else
		return;
}

map<unsigned, RegExp *> NFA::_initREMap(unsigned state) const {
	map<unsigned, set<char> > initial;
	map<unsigned, RegExp *> res;
	for( multimap<pair<unsigned, char>, unsigned>::const_iterator it = rules . begin();
												it != rules . end(); ++it)
		if (it -> first . first == state)
			initial[it -> second] . insert(it -> first . second);
	map<unsigned, set<char> >::const_iterator iti = initial . begin();
	for( ; iti != initial . end(); ++iti )
		res[iti -> first] = _charSetToRegExp(iti -> second);	
	return res;
}

void NFA::_freeREMap(map<unsigned, RegExp *> const & rem) {
	for(map<unsigned, RegExp *>::const_iterator it = rem . begin();
							it != rem . end(); ++it )
		delete it->second;
}	

void nicePrintREMap(map<unsigned, RegExp *> const & rem) {
	for( map<unsigned, RegExp *>::const_iterator it = rem . begin() ; it != rem . end(); ++it )
		cout << it -> first << " " << it -> second -> toString() << endl;
}

RegExp * NFA::_toRegExp() const {
	map<unsigned, map<unsigned, RegExp *> > substitution;
	vector<unsigned> order;
	map<unsigned, RegExp *> stmap;
	map<unsigned, RegExp *> remap;
	map<unsigned, RegExp *>::iterator stit;
	substitution[* starting . begin()] = _initREMap(* starting . begin());
	_applyREMap(* starting . begin(), substitution[* starting . begin()],
				* starting . begin(), substitution[* starting . begin()]);
	order . push_back(* starting . begin());
	//cout << "remap for " << * starting . begin() << " is " << endl;
	//nicePrintREMap(substitution[* starting . begin()]);
	while (substitution[* starting . begin()] . size() > 0 &&
			(substitution[* starting . begin()] . size() > 1 ||
			substitution[* starting . begin()] . find(0) ==
			substitution[* starting . begin()] . end())) {
		stit = substitution[* starting . begin()] . begin();
		if (stit -> first == 0)
			++stit;
		remap = _initREMap(stit -> first);
		_applyREMap(stit -> first, remap, stit -> first, remap);
		for( vector<unsigned>::const_iterator itv = order . begin(); itv != order . end(); ++itv ) {
			_applyREMap(*itv, substitution[*itv], stit -> first, remap);
			_applyREMap(stit -> first, remap, stit -> first, remap);
		}
		for( vector<unsigned>::const_iterator itv = order . begin(); itv != order . end(); ++itv ) {
			_applyREMap(stit -> first, remap, *itv, substitution[*itv]);
			_applyREMap(*itv, substitution[*itv], *itv, substitution[*itv]);
			//cout << "remap for " << *itv << " is " << endl;
			//nicePrintREMap(substitution[*itv]);
		}
		substitution[stit -> first] = remap;
		order . push_back(stit -> first);
	}
	stmap = substitution[* starting . begin()];
	if (stmap . size() == 0) {
		for( vector<unsigned>::const_iterator itv = order . begin(); itv != order . end(); ++itv ) {
			_freeREMap(substitution[*itv]);
		}
		return new EmptyRegExp();
	} else {
		RegExp * res = stmap[0] -> copy();
		for( vector<unsigned>::const_iterator itv = order . begin(); itv != order . end(); ++itv ) {
			_freeREMap(substitution[*itv]);
		}
		return res;
	}
}
